package com.zjj.algorithm.learning.dmsxl.greed;

import java.util.Arrays;

/**
 * 135. 分发糖果 困难
 * <p>
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * <p>
 * 你需要按照以下要求，给这些孩子分发糖果：
 * <p>
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子评分更高的孩子会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：ratings = [1,0,2]
 * 输出：5
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
 * 示例 2：
 * <p>
 * 输入：ratings = [1,2,2]
 * 输出：4
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
 * 第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 * <p>
 * <p>
 * 提示：
 * <p>
 * n == ratings.length
 * 1 <= n <= 2 * 104
 * 0 <= ratings[i] <= 2 * 104
 *
 * @author zjj_admin
 * @date 2023/2/2 23:01
 */
public class Greed_12_Candy {

    public static void main(String[] args) {
        int[] ratings = new int[]{1, 2, 87, 87, 87, 2, 1};
        int res = candy(ratings);
        System.out.println("res = " + res);

    }


    /**
     * 使用贪心算法
     * 先从左到右遍历，当右边的孩子分数大的话就将糖果数 + 1。
     * <p>
     * 时间
     * 2 ms
     * 击败
     * 98.57%
     * 内存
     * 41.8 MB
     * 击败
     * 85.95%
     *
     * @param ratings
     * @return
     */
    public static int candy(int[] ratings) {
        int[] nums = new int[ratings.length];
        Arrays.fill(nums, 1);
        //先从左向右遍历
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                nums[i] = nums[i - 1] + 1;
            } else {
                nums[i] = 1;
            }
        }
        //再从右向左遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            //当左边的大于右边的时
            if (ratings[i] > ratings[i + 1]) {
                nums[i] = Math.max(nums[i], nums[i + 1] + 1);
            }
        }
        int res = 0;
        for (int num : nums) {
            res += num;
        }
        return res;
    }
}
